package com.lili.math;

import java.util.*;

/**
 * @Auther: 李 力
 * @Date: 2024/8/5
 * @Description: 丑数
 * @version: 1.0
 */
public class LeetCode168 {
    /*
     *  时间复杂度: O(nlogn)
     *  空间复杂度: O(n)
     */
    public static int nthUglyNumber(int n) {
        int[] factors = {2, 3, 5};
        HashSet<Long> seen = new HashSet<>();
        PriorityQueue<Long> heap = new PriorityQueue<>();
        seen.add(1L);
        heap.offer(1L);
        long result = 0;
        for (int i = 0; i < n; i++) {
            Long curr = heap.poll();
            result = curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return Integer.parseInt(Long.toString(result));
    }
}
